#include <stdio.h>
#include <stdlib.h>
typedef struct node {
    char data;
    struct node *left;
    struct node *right;
} Node,*BinaryTree;
char str[20]={"ABC**DE*G**F***"};

// 创建二叉树
BinaryTree create_BinaryTree();

// 先序遍历
void preOrder(BinaryTree T);

// 中序遍历
void inOrder(BinaryTree T);

// 后序遍历
void postOrder(BinaryTree T);

//销毁二叉树
void destroy_BinaryTree(BinaryTree *T);

//删除一个节点
void delete_Node(BinaryTree *T,char data);

//打印二叉树
void print_BinaryTree(BinaryTree T);


int main(int argc, char const *argv[])
{
    BinaryTree T;
    T=create_BinaryTree();
    printf("先序遍历:");
    preOrder(T);
    printf("\n");
    printf("中序遍历:");
    inOrder(T);
    printf("\n");
    printf("后序遍历:");
    postOrder(T);
    printf("\n");
    printf("打印二叉树:");
    print_BinaryTree(T);
    printf("\n");
    delete_Node(&T,'D');
    printf("删除节点D后的二叉树:");
    preOrder(T);
    printf("\n");
    destroy_BinaryTree(&T);
    return 0;
}

//创建二叉树
BinaryTree create_BinaryTree()
{
    static int i=0;
    if (str[i]=='*')
    {
        i++;
        return NULL;
    }

    BinaryTree T=(BinaryTree)malloc(sizeof(Node));
    if (T == NULL)
    {
        printf("内存分配失败\n");
        exit(1);
    }
    T->data=str[i];
    i++;
    T->left=create_BinaryTree();
    T->right=create_BinaryTree();
    return T;
    
}

// 先序遍历
void preOrder(BinaryTree T)
{
    if (T!=NULL)
    {
        printf("%c ",T->data);
        preOrder(T->left);
        preOrder(T->right);
    }
}

// 中序遍历
void inOrder(BinaryTree T)
{
    if (T!=NULL)
    {
        inOrder(T->left);
        printf("%c ",T->data);
        inOrder(T->right);
    }
}

// 后序遍历
void postOrder(BinaryTree T)
{
    if (T!=NULL)
    {
        postOrder(T->left);
        postOrder(T->right);
        printf("%c ",T->data);
    }
}

//销毁二叉树
void destroy_BinaryTree(BinaryTree *T)
{
    if (*T!=NULL)
    {
        destroy_BinaryTree(&(*T)->left);
        destroy_BinaryTree(&(*T)->right);
        free(*T);
        *T=NULL;
    }
}

//删除一个节点
void delete_Node(BinaryTree *T,char data)
{
    if (*T!=NULL)
    {
        if ((*T)->data==data)
        {
            destroy_BinaryTree(T);
        }
        else
        {
            delete_Node(&(*T)->left,data);
            delete_Node(&(*T)->right,data);
        }
    }
}

void print_BinaryTree(BinaryTree T)
{
    if (T!=NULL)
    {
        printf("%c",T->data);
        if (T->left!=NULL || T->right!=NULL)
        {
            printf("(");
            print_BinaryTree(T->left);
            if (T->right!=NULL)
            {
                printf(",");
            }
            print_BinaryTree(T->right);
            printf(")");
        }
    }
}
    